//////////////////////////////////////////////////////////////////////////
//
// GAM203
// Renderer Class
// Renderer.cpp
// 
// Grant Johnson
// Qantm College
// 27/10/2010
//
//////////////////////////////////////////////////////////////////////////


#include "Renderer.h"
#include "DXMgr.h"
#include "Drawable.h"
#include "Light.h"
#include "Text.h"
#include <assert.h>
#include "Octree.h"
#include <d3d9.h>
#include <d3dx9.h>
#include "Emitter.h"
#include "DXMgr.h"
#include "InputMgr.h" // check

Renderer* Singleton<Renderer>::m_pInstance = NULL;

Renderer::Renderer()
: m_debugLineCount(0)
, m_pDebugLineData(NULL)
, m_pDebugLineVertexBuf(NULL)
, m_pFpsText(NULL)
, m_pOctree(NULL)
, m_width(0)
, m_height(0)
{
	m_pFpsBuffer = new char[256];
}
Renderer::~Renderer()
{
	if (m_pDebugLineData)
	{
		delete[] m_pDebugLineData;
		m_pDebugLineData = NULL;
	}

	if (m_pDebugLineVertexBuf)
	{
		m_pDebugLineVertexBuf->Release();
		m_pDebugLineVertexBuf = NULL;
	}
	if(m_pFpsText)
	{
		delete m_pFpsText;
		m_pFpsText = NULL;
	}
	if(m_pFpsBuffer)
	{
		delete m_pFpsBuffer;
		m_pFpsBuffer = NULL;
	}
	if(m_pOctree)
	{
		delete m_pOctree;
		m_pOctree = NULL;
	}
	RemoveAll();
}
bool Renderer::Setup(IDirect3DDevice9* a_pDevice, float a_width, float a_height)
{
	// Create a data buffer for debug line vertices
	const int debugLineVertCount = MAX_DEBUG_LINES * 2;  // *2 = two points per line
	m_pDebugLineData = new DebugLineVertexData[debugLineVertCount];  

	// Create a vertex buffer for debug lines
	const int vertexBufferSizeBytes = sizeof(DebugLineVertexData) * debugLineVertCount;
	a_pDevice->CreateVertexBuffer(vertexBufferSizeBytes, 0, DEBUG_LINE_FVF, D3DPOOL_DEFAULT, &m_pDebugLineVertexBuf, NULL);
	// Assume it works; if it fails, m_pDebugLineVertexBuf will just be NULL
	if(m_pDebugLineVertexBuf == NULL)
	{
		return false;
	}

	//Setup the renderer dimensions
	m_width = a_width;
	m_height = a_height;

	//Create FPS text
	m_instantFps = 0.0f;
	m_filteredFps = 0.0f;
	m_pFpsText = new Text();
	m_pFpsText->CreateObject(DXMgr::GetInstance().GetDevice(), NULL, 14, "Instant Fps: [0.0]\nFiltered Fps: [0.0]", 10, 10, D3DCOLOR_XRGB(255,255,255));

	m_pShadowDecl = NULL;
    if(FAILED(a_pDevice->CreateVertexDeclaration(Decl, &m_pShadowDecl)))
	{
		return false;
	}

	return true;
}
bool Renderer::AddObject(Drawable* a_pObject)
{
	for(DrawableObjectList::iterator it = m_drawableObjects.begin(); it != m_drawableObjects.end(); it++)
	{
		assert(a_pObject != *it);
	}
	if (!a_pObject)
	{
		return false;
	}

	m_drawableObjects.push_back(a_pObject);

	return true;
}

bool Renderer::RemoveObject(Drawable* a_pObject)
{
	// Look for this object in our list
	for (DrawableObjectList::iterator iter = m_drawableObjects.begin(); iter != m_drawableObjects.end(); ++iter)
	{
		Drawable* pElem = *iter;
		if (pElem == a_pObject)
		{
			// Found the object! Remove it from the list
			m_drawableObjects.erase(iter);
			return true;
		}
	}
	return false;  // Not found
}
bool Renderer::AddOctreeObject(Drawable* a_pObject)
{
	for(DrawableObjectList::iterator it = m_octreeObjects.begin(); it != m_octreeObjects.end(); it++)
	{
		assert(a_pObject != *it);
	}
	if (!a_pObject)
	{
		return false;
	}

	m_octreeObjects.push_back(a_pObject);

	return true;
}

bool Renderer::RemoveOctreeObject(Drawable* a_pObject)
{
	// Look for this object in our list
	for (DrawableObjectList::iterator iter = m_octreeObjects.begin(); iter != m_octreeObjects.end(); ++iter)
	{
		Drawable* pElem = *iter;
		if (pElem == a_pObject)
		{
			// Found the object! Remove it from the list
			m_octreeObjects.erase(iter);
			return true;
		}
	}
	return false;  // Not found
}
bool Renderer::AddEmitter(Emitter* a_pEmitter)
{
	for(EmitterList::iterator it = m_emitters.begin(); it != m_emitters.end(); it++)
	{
		assert(a_pEmitter != *it);
	}
	if (!a_pEmitter)
	{
		return false;
	}

	m_emitters.push_back(a_pEmitter);

	return true;
}

bool Renderer::RemoveEmitter(Emitter* a_pEmitter)
{
	// Look for this object in our list
	for (EmitterList::iterator iter = m_emitters.begin(); iter != m_emitters.end(); ++iter)
	{
		Emitter* pElem = *iter;
		if (pElem == a_pEmitter)
		{
			// Found the object! Remove it from the list
			m_emitters.erase(iter);
			return true;
		}
	}
	return false;  // Not found
}
bool Renderer::AddText(Drawable* a_pObject)
{
	DrawableObjectList::iterator it;
	for(it = m_textObjects.begin(); it != m_textObjects.end(); it++)
	{
		assert(a_pObject != *it);
	}
	if (!a_pObject)
	{
		return false;
	}

	m_textObjects.push_back(a_pObject);

	return true;
}

bool Renderer::RemoveText(Drawable* a_pObject)
{
	// Look for this object in our list
	for (DrawableObjectList::iterator iter = m_textObjects.begin(); iter != m_textObjects.end(); ++iter)
	{
		Drawable* pElem = *iter;
		if (pElem == a_pObject)
		{
			// Found the object! Remove it from the list
			m_textObjects.erase(iter);
			return true;
		}
	}
	return false;  // Not found
}
bool Renderer::AddStencil(Drawable* a_pObject)
{
	DrawableObjectList::iterator it;
	for(it = m_stencilObjects.begin(); it != m_stencilObjects.end(); it++)
	{
		assert(a_pObject != *it);
	}
	if (!a_pObject)
	{
		return false;
	}

	m_stencilObjects.push_back(a_pObject);

	return true;
}

bool Renderer::RemoveStencil(Drawable* a_pObject)
{
	// Look for this object in our list
	for (DrawableObjectList::iterator iter = m_stencilObjects.begin(); iter != m_stencilObjects.end(); ++iter)
	{
		Drawable* pElem = *iter;
		if (pElem == a_pObject)
		{
			// Found the object! Remove it from the list
			m_stencilObjects.erase(iter);
			return true;
		}
	}
	return false;  // Not found
}

bool Renderer::AddLight(Light* a_pLight)
{
	if (!a_pLight)
	{
		return false;
	}

	m_lights.push_back(a_pLight);

	return true;
}

bool Renderer::RemoveLight(Light* a_pLight)
{
	// Look for this light in our list
	for (LightList::iterator iter = m_lights.begin(); iter != m_lights.end(); ++iter)
	{
		Light* pElem = *iter;
		if (pElem == a_pLight)
		{
			// Found the light! Remove it from the list
			m_lights.erase(iter);
			return true;
		}
	}
	return false;  // Not found
}

bool Renderer::Render(float a_dt, IDirect3DDevice9* a_pDevice)
{
	// Clear backbuffer
	a_pDevice->Clear(0, NULL, D3DCLEAR_TARGET | D3DCLEAR_ZBUFFER | D3DCLEAR_STENCIL, D3DCOLOR_XRGB(15, 15, 15), 1.0f, 0);

	// Create our projection matrix for this frame
	D3DXMATRIX viewToScreen;	
	D3DXMatrixPerspectiveFovLH(&viewToScreen, 3.14f / 4, m_width/m_height, 1, 1000);

	
	//Update the cameras frustum and get position for render params
	D3DXVECTOR3 cameraPos(0.0f, 0.0f, 0.0f);
	D3DXMATRIX worldToView;
	if(GetActiveCamera() != NULL)
	{
		GetActiveCamera()->Update(a_dt);
		GetActiveCamera()->GetViewMatrix(worldToView);
		GetActiveCamera()->UpdateFrustum(worldToView*viewToScreen);
		cameraPos = GetActiveCamera()->GetEyePos();
	}

	// Set up common render states
	//setup depth/z buffer
	a_pDevice->SetRenderState(D3DRS_ZENABLE, TRUE);
	a_pDevice->SetRenderState(D3DRS_ZFUNC, D3DCMP_LESS);

	D3DXCOLOR globalAmbient(20.0f, 20.0f, 20.0f, 255.0f);
	RenderParams renderParams(worldToView, viewToScreen, cameraPos, globalAmbient);

	// Begin rendering
	a_pDevice->BeginScene();

	// Set up lights
	int curLightId = 0;
	for (LightList::iterator iter = m_lights.begin(); iter != m_lights.end(); ++iter)
	{
		Light* pElem = *iter;
		renderParams.AddLight(&pElem->GetLightData());
		++curLightId;
	}

	//Pre render with the stencils
	for (DrawableObjectList::iterator iter = m_stencilObjects.begin(); iter != m_stencilObjects.end(); ++iter)
	{
		//setup stencil
		a_pDevice->SetRenderState(D3DRS_ZENABLE, false);

		a_pDevice->SetRenderState(D3DRS_STENCILZFAIL, D3DSTENCILOP_KEEP);	
		a_pDevice->SetRenderState(D3DRS_STENCILPASS, D3DSTENCILOP_REPLACE);	

		//Enable stencil buffer rendering, and draw 1's where anything is drawn
		a_pDevice->SetRenderState(D3DRS_STENCILENABLE, true);	
		a_pDevice->SetRenderState(D3DRS_STENCILFUNC, D3DCMP_ALWAYS);
		a_pDevice->SetRenderState(D3DRS_STENCILREF, 1);

		//Draw the first item into the stencil buffer, fills with 1's where it draws
		Drawable* pElem = *iter;
		pElem->Render(a_dt, a_pDevice, renderParams);
		//draw shadow
		a_pDevice->SetRenderState(D3DRS_ZENABLE, true);
	}


	//Toggle rendering types
	if(m_pOctree)
	{
		if(m_pOctree->GetWireframeRendering())
			DXMgr::GetInstance().GetDevice()->SetRenderState(D3DRS_FILLMODE, D3DFILL_WIREFRAME);
		else if(!m_pOctree->GetWireframeRendering())
			DXMgr::GetInstance().GetDevice()->SetRenderState(D3DRS_FILLMODE, D3DFILL_SOLID);

		//Clear the previous list of objects
		m_octreeObjectsToRender.clear();

		//Refil list with new objects to be rendered
		m_pOctree->FillRenderList();

		//Render the octree
		for(DrawableObjectList::iterator iter = m_octreeObjects.begin(); iter != m_octreeObjects.end(); ++iter)
		{
			Drawable* pElem = *iter;
			a_pDevice->SetRenderState(D3DRS_STENCILENABLE, false);
			pElem->Render(a_dt, a_pDevice, renderParams);

			//Something like this setup for shadow volumes
			//pElem->RenderShadow(a_dt, a_pDevice, renderParams);
		}
	}

	//Render non octree objects
	for(DrawableObjectList::iterator iter = m_drawableObjects.begin(); iter != m_drawableObjects.end(); ++iter)
	{
		Drawable* pElem = *iter;
		a_pDevice->SetRenderState(D3DRS_STENCILENABLE, false);
		pElem->Render(a_dt, a_pDevice, renderParams);
	}

	//Drawing stencils
	/*if(pElem->DoesDrawOverStencil())
	{	
		a_pDevice->SetRenderState(D3DRS_STENCILENABLE, true);
		//Set to only draw where the value is 1
		a_pDevice->SetRenderState(D3DRS_STENCILFUNC, D3DCMP_EQUAL);
		//Draw item over the stencil
		pElem->Render(a_dt, a_pDevice, renderParams);			
	}*/

	//Render All Particle Emitters
	for(EmitterList::iterator iter = m_emitters.begin(); iter != m_emitters.end(); iter++)
	{
		Emitter* pElem = *iter;
		if (pElem)
		{
			//Update the particles
			pElem->Update(a_dt);
			//Render the particles
			pElem->Render(a_dt, a_pDevice, renderParams);
		}
	}

	//Render text
	for(DrawableObjectList::iterator iter = m_textObjects.begin(); iter != m_textObjects.end(); ++iter)
	{
		Drawable* pElem = *iter;
		a_pDevice->SetRenderState(D3DRS_STENCILENABLE, false);
		pElem->Render(a_dt, a_pDevice, renderParams);
	}

	//Update and Render Frame per second text
	UpdateFps(a_dt);
	m_pFpsText->Render(a_dt, a_pDevice, renderParams);

	// Render debug lines
	if (m_debugLineCount && m_pDebugLineData && m_pDebugLineVertexBuf)
	{
		// Copy data into vertex buffer for rendering
		void* pLockedData = NULL;
		const int vertexDataSizeBytes = sizeof(DebugLineVertexData) * 2 * m_debugLineCount;
		HRESULT result = m_pDebugLineVertexBuf->Lock(0, vertexDataSizeBytes, &pLockedData, 0);
		if (result == D3D_OK)
		{
			memcpy(pLockedData, m_pDebugLineData, vertexDataSizeBytes);
			m_pDebugLineVertexBuf->Unlock();
			pLockedData = NULL;

			// Disable lighting for debug lines
			a_pDevice->SetRenderState(D3DRS_LIGHTING, FALSE);
			a_pDevice->SetTexture(0, NULL);

			//Clear out any previously set world transform
			D3DXMATRIX identityMat;
			D3DXMatrixIdentity(&identityMat);
			a_pDevice->SetTransform(D3DTS_WORLD, &identityMat);

			// Send data to GPU
			a_pDevice->SetStreamSource(0, m_pDebugLineVertexBuf, 0, sizeof(DebugLineVertexData));
			a_pDevice->SetFVF(DEBUG_LINE_FVF);
			a_pDevice->DrawPrimitive(D3DPT_LINELIST, 0, m_debugLineCount);
		}
	}

	// Debug lines have been rendered; throw data away by resetting count
	m_debugLineCount = 0;

	// Finish rendering
	a_pDevice->EndScene();

	// Display the backbuffer
	a_pDevice->Present(NULL, NULL, NULL, NULL);

	return true;
}

bool Renderer::AddDebugLine(const D3DVECTOR& a_start, const D3DVECTOR& a_end, D3DCOLOR a_colour)
{
	if (m_pDebugLineData && m_debugLineCount < MAX_DEBUG_LINES)
	{
		// Insert start vertex
		DebugLineVertexData& startVert = m_pDebugLineData[m_debugLineCount * 2];
		startVert.pos = a_start;
		startVert.col = a_colour;

		// Insert end vertex
		DebugLineVertexData& endVert = m_pDebugLineData[m_debugLineCount * 2 + 1];
		endVert.pos = a_end;
		endVert.col = a_colour;

		++m_debugLineCount;

		return true;
	}

	return false;  // Buffer is full or unavailable
}

void Renderer::RemoveAll()
{
	//Remove all emitters - this needs to be changed to just a clear call
	for(EmitterList::iterator iter = m_emitters.begin(); iter != m_emitters.end(); ++iter)
	{
		Emitter* pElem = *iter;
		delete pElem;
		pElem = NULL;
	}
	m_emitters.clear();


	//Remove all lights - this also needs to be changed to just a clear call
	for(LightList::iterator iter = m_lights.begin(); iter != m_lights.end(); ++iter)
	{
		Light* pElem = *iter;
		delete pElem;
		pElem = NULL;
	}
	m_lights.clear();

	//These are only pointers to objects stored elsewhere, so just clear the list
	m_octreeObjects.clear();
	m_drawableObjects.clear();
	m_textObjects.clear();
	m_stencilObjects.clear();
}
void Renderer::UpdateFps(float a_dt)
{
	m_instantFps = 1/a_dt;
	m_filteredFps = ((m_filteredFps*29)+m_instantFps)/30;
	sprintf_s(m_pFpsBuffer, 256, "Instant FPS: [%0.1f] \nFiltered FPS: [%0.1f]", m_instantFps, m_filteredFps);
	m_pFpsText->SetText(m_pFpsBuffer);
}
void Renderer::GenerateOctree(int a_max, float a_bottomLeft, float a_topRight)
{
	//Clean up if there is already one created
	if(m_pOctree)
	{
		RemoveText(m_pOctree->GetDebugText());
		delete m_pOctree;
		m_pOctree = NULL;
	}
	if(m_pOctree == NULL)
	{
		//Setup octree rendering
		m_pOctree = new Octree(a_max);
		m_pOctree->CreateOctree(AABB(D3DXVECTOR3(a_bottomLeft, a_bottomLeft, a_bottomLeft), D3DXVECTOR3(a_topRight, a_topRight, a_topRight)));
	}
}
void Renderer::SetDimensions(float a_width, float a_height)
{ 
	m_width = a_width;
	m_height = a_height; 
	DXMgr::GetInstance().Resize();
}
bool Renderer::AddCamera(ABCamera* a_pCamera)
{
	if(a_pCamera)
	{
		for(CameraList::iterator iter = m_cameras.begin(); iter != m_cameras.end(); ++iter)
		{
			ABCamera* pElem = *iter;
			if(pElem == a_pCamera)
			{
				return false;
			}
		}
		//Wasnt found, so add to list
		m_cameras.push_back(a_pCamera);
		return true;
	}
	return false;
}
bool Renderer::RemoveCamera(ABCamera* a_pCamera)
{
	if(a_pCamera)
	{
		for(CameraList::iterator iter = m_cameras.begin(); iter != m_cameras.end(); ++iter)
		{
			ABCamera* pElem = *iter;
			if(pElem == a_pCamera)
			{
				//Found the object, remove it
				iter = m_cameras.erase(iter);
				return true;
			}
		}
	}
	return false;
}
ABCamera* Renderer::GetActiveCamera()
{
	for(CameraList::iterator iter = m_cameras.begin(); iter != m_cameras.end(); ++iter)
	{
		ABCamera* pElem = *iter;
		if(pElem->IsActive())
		{
			//This camera was active, so return it
			return pElem;
		}
	}
	//No active cameras
	return NULL;
}
HRESULT Renderer::GenerateShadowMesh( IDirect3DDevice9* pd3dDevice, ID3DXMesh* pMesh, ID3DXMesh** ppOutMesh )
{
	HRESULT hr = S_OK;
	ID3DXMesh* pInputMesh;

	if( !ppOutMesh )
		return E_INVALIDARG;
	*ppOutMesh = NULL;

	// Convert the input mesh to a format same as the output mesh using 32-bit index.
	hr = pMesh->CloneMesh( D3DXMESH_32BIT, Decl, pd3dDevice, &pInputMesh );
	if( FAILED( hr ) )
		return hr;

	// Generate adjacency information
	DWORD* pdwAdj = new DWORD[3 * pInputMesh->GetNumFaces()];
	DWORD* pdwPtRep = new DWORD[pInputMesh->GetNumVertices()];
	if( !pdwAdj || !pdwPtRep )
	{
		delete[] pdwAdj; delete[] pdwPtRep;
		pInputMesh->Release();
		return E_OUTOFMEMORY;
	}

	hr = pInputMesh->GenerateAdjacency( 0.0001f, pdwAdj );
	if( FAILED( hr ) )
	{
		delete[] pdwAdj; delete[] pdwPtRep;
		pInputMesh->Release();
		return hr;
	}

	pInputMesh->ConvertAdjacencyToPointReps( pdwAdj, pdwPtRep );
	delete[] pdwAdj;

	SHADOWVERT* pVBData = NULL;
	DWORD* pdwIBData = NULL;

	pInputMesh->LockVertexBuffer( 0, ( LPVOID* )&pVBData );
	pInputMesh->LockIndexBuffer( 0, ( LPVOID* )&pdwIBData );

	if( pVBData && pdwIBData )
	{
		// Maximum number of unique edges = Number of faces * 3
		DWORD dwNumEdges = pInputMesh->GetNumFaces() * 3;
		CEdgeMapping* pMapping = new CEdgeMapping[dwNumEdges];
		if( pMapping )
		{
			int nNumMaps = 0;  // Number of entries that exist in pMapping

			// Create a new mesh
			ID3DXMesh* pNewMesh;
			hr = D3DXCreateMesh( pInputMesh->GetNumFaces() + dwNumEdges * 2,
				pInputMesh->GetNumFaces() * 3,
				D3DXMESH_32BIT,
				Decl,
				pd3dDevice,
				&pNewMesh );
			if( SUCCEEDED( hr ) )
			{
				SHADOWVERT* pNewVBData = NULL;
				DWORD* pdwNewIBData = NULL;

				pNewMesh->LockVertexBuffer( 0, ( LPVOID* )&pNewVBData );
				pNewMesh->LockIndexBuffer( 0, ( LPVOID* )&pdwNewIBData );

				// nNextIndex is the array index in IB that the next vertex index value
				// will be store at.
				int nNextIndex = 0;

				if( pNewVBData && pdwNewIBData )
				{
					ZeroMemory( pNewVBData, pNewMesh->GetNumVertices() * pNewMesh->GetNumBytesPerVertex() );
					ZeroMemory( pdwNewIBData, sizeof( DWORD ) * pNewMesh->GetNumFaces() * 3 );

					// pNextOutVertex is the location to write the next
					// vertex to.
					SHADOWVERT* pNextOutVertex = pNewVBData;

					// Iterate through the faces.  For each face, output new
					// vertices and face in the new mesh, and write its edges
					// to the mapping table.

					for( UINT f = 0; f < pInputMesh->GetNumFaces(); ++f )
					{
						// Copy the vertex data for all 3 vertices
						CopyMemory( pNextOutVertex, pVBData + pdwIBData[f * 3], sizeof( SHADOWVERT ) );
						CopyMemory( pNextOutVertex + 1, pVBData + pdwIBData[f * 3 + 1], sizeof( SHADOWVERT ) );
						CopyMemory( pNextOutVertex + 2, pVBData + pdwIBData[f * 3 + 2], sizeof( SHADOWVERT ) );

						// Write out the face
						pdwNewIBData[nNextIndex++] = f * 3;
						pdwNewIBData[nNextIndex++] = f * 3 + 1;
						pdwNewIBData[nNextIndex++] = f * 3 + 2;

						// Compute the face normal and assign it to
						// the normals of the vertices.
						D3DXVECTOR3 v1, v2;  // v1 and v2 are the edge vectors of the face
						D3DXVECTOR3 vNormal;
						v1 = *( D3DXVECTOR3* )( pNextOutVertex + 1 ) - *( D3DXVECTOR3* )pNextOutVertex;
						v2 = *( D3DXVECTOR3* )( pNextOutVertex + 2 ) - *( D3DXVECTOR3* )( pNextOutVertex + 1 );
						D3DXVec3Cross( &vNormal, &v1, &v2 );
						D3DXVec3Normalize( &vNormal, &vNormal );

						pNextOutVertex->Normal = vNormal;
						( pNextOutVertex + 1 )->Normal = vNormal;
						( pNextOutVertex + 2 )->Normal = vNormal;

						pNextOutVertex += 3;

						// Add the face's edges to the edge mapping table

						// Edge 1
						int nIndex;
						int nVertIndex[3] =
						{
							pdwPtRep[pdwIBData[f * 3]],
							pdwPtRep[pdwIBData[f * 3 + 1]],
							pdwPtRep[pdwIBData[f * 3 + 2]]
						};
						nIndex = FindEdgeInMappingTable( nVertIndex[0], nVertIndex[1], pMapping, dwNumEdges );

						// If error, we are not able to proceed, so abort.
						if( -1 == nIndex )
						{
							hr = E_INVALIDARG;
							goto cleanup;
						}

						if( pMapping[nIndex].m_anOldEdge[0] == -1 && pMapping[nIndex].m_anOldEdge[1] == -1 )
						{
							// No entry for this edge yet.  Initialize one.
							pMapping[nIndex].m_anOldEdge[0] = nVertIndex[0];
							pMapping[nIndex].m_anOldEdge[1] = nVertIndex[1];
							pMapping[nIndex].m_aanNewEdge[0][0] = f * 3;
							pMapping[nIndex].m_aanNewEdge[0][1] = f * 3 + 1;

							++nNumMaps;
						}
						else
						{
							// An entry is found for this edge.  Create
							// a quad and output it.
							assert( nNumMaps > 0 );

							pMapping[nIndex].m_aanNewEdge[1][0] = f * 3;      // For clarity
							pMapping[nIndex].m_aanNewEdge[1][1] = f * 3 + 1;

							// First triangle
							pdwNewIBData[nNextIndex++] = pMapping[nIndex].m_aanNewEdge[0][1];
							pdwNewIBData[nNextIndex++] = pMapping[nIndex].m_aanNewEdge[0][0];
							pdwNewIBData[nNextIndex++] = pMapping[nIndex].m_aanNewEdge[1][0];

							// Second triangle
							pdwNewIBData[nNextIndex++] = pMapping[nIndex].m_aanNewEdge[1][1];
							pdwNewIBData[nNextIndex++] = pMapping[nIndex].m_aanNewEdge[1][0];
							pdwNewIBData[nNextIndex++] = pMapping[nIndex].m_aanNewEdge[0][0];

							// pMapping[nIndex] is no longer needed. Copy the last map entry
							// over and decrement the map count.

							pMapping[nIndex] = pMapping[nNumMaps - 1];
							FillMemory( &pMapping[nNumMaps - 1], sizeof( pMapping[nNumMaps - 1] ), 0xFF );
							--nNumMaps;
						}

						// Edge 2
						nIndex = FindEdgeInMappingTable( nVertIndex[1], nVertIndex[2], pMapping, dwNumEdges );

						// If error, we are not able to proceed, so abort.
						if( -1 == nIndex )
						{
							hr = E_INVALIDARG;
							goto cleanup;
						}

						if( pMapping[nIndex].m_anOldEdge[0] == -1 && pMapping[nIndex].m_anOldEdge[1] == -1 )
						{
							pMapping[nIndex].m_anOldEdge[0] = nVertIndex[1];
							pMapping[nIndex].m_anOldEdge[1] = nVertIndex[2];
							pMapping[nIndex].m_aanNewEdge[0][0] = f * 3 + 1;
							pMapping[nIndex].m_aanNewEdge[0][1] = f * 3 + 2;

							++nNumMaps;
						}
						else
						{
							// An entry is found for this edge.  Create
							// a quad and output it.
							assert( nNumMaps > 0 );

							pMapping[nIndex].m_aanNewEdge[1][0] = f * 3 + 1;
							pMapping[nIndex].m_aanNewEdge[1][1] = f * 3 + 2;

							// First triangle
							pdwNewIBData[nNextIndex++] = pMapping[nIndex].m_aanNewEdge[0][1];
							pdwNewIBData[nNextIndex++] = pMapping[nIndex].m_aanNewEdge[0][0];
							pdwNewIBData[nNextIndex++] = pMapping[nIndex].m_aanNewEdge[1][0];

							// Second triangle
							pdwNewIBData[nNextIndex++] = pMapping[nIndex].m_aanNewEdge[1][1];
							pdwNewIBData[nNextIndex++] = pMapping[nIndex].m_aanNewEdge[1][0];
							pdwNewIBData[nNextIndex++] = pMapping[nIndex].m_aanNewEdge[0][0];

							// pMapping[nIndex] is no longer needed. Copy the last map entry
							// over and decrement the map count.

							pMapping[nIndex] = pMapping[nNumMaps - 1];
							FillMemory( &pMapping[nNumMaps - 1], sizeof( pMapping[nNumMaps - 1] ), 0xFF );
							--nNumMaps;
						}

						// Edge 3
						nIndex = FindEdgeInMappingTable( nVertIndex[2], nVertIndex[0], pMapping, dwNumEdges );

						// If error, we are not able to proceed, so abort.
						if( -1 == nIndex )
						{
							hr = E_INVALIDARG;
							goto cleanup;
						}

						if( pMapping[nIndex].m_anOldEdge[0] == -1 && pMapping[nIndex].m_anOldEdge[1] == -1 )
						{
							pMapping[nIndex].m_anOldEdge[0] = nVertIndex[2];
							pMapping[nIndex].m_anOldEdge[1] = nVertIndex[0];
							pMapping[nIndex].m_aanNewEdge[0][0] = f * 3 + 2;
							pMapping[nIndex].m_aanNewEdge[0][1] = f * 3;

							++nNumMaps;
						}
						else
						{
							// An entry is found for this edge.  Create
							// a quad and output it.
							assert( nNumMaps > 0 );

							pMapping[nIndex].m_aanNewEdge[1][0] = f * 3 + 2;
							pMapping[nIndex].m_aanNewEdge[1][1] = f * 3;

							// First triangle
							pdwNewIBData[nNextIndex++] = pMapping[nIndex].m_aanNewEdge[0][1];
							pdwNewIBData[nNextIndex++] = pMapping[nIndex].m_aanNewEdge[0][0];
							pdwNewIBData[nNextIndex++] = pMapping[nIndex].m_aanNewEdge[1][0];

							// Second triangle
							pdwNewIBData[nNextIndex++] = pMapping[nIndex].m_aanNewEdge[1][1];
							pdwNewIBData[nNextIndex++] = pMapping[nIndex].m_aanNewEdge[1][0];
							pdwNewIBData[nNextIndex++] = pMapping[nIndex].m_aanNewEdge[0][0];

							// pMapping[nIndex] is no longer needed. Copy the last map entry
							// over and decrement the map count.

							pMapping[nIndex] = pMapping[nNumMaps - 1];
							FillMemory( &pMapping[nNumMaps - 1], sizeof( pMapping[nNumMaps - 1] ), 0xFF );
							--nNumMaps;
						}
					}

					// Now the entries in the edge mapping table represent
					// non-shared edges.  What they mean is that the original
					// mesh has openings (holes), so we attempt to patch them.
					// First we need to recreate our mesh with a larger vertex
					// and index buffers so the patching geometry could fit.

					// Create a mesh with large enough vertex and
					// index buffers.

					SHADOWVERT* pPatchVBData = NULL;
					DWORD* pdwPatchIBData = NULL;

					ID3DXMesh* pPatchMesh = NULL;
					// Make enough room in IB for the face and up to 3 quads for each patching face
					hr = D3DXCreateMesh( nNextIndex / 3 + nNumMaps * 7,
						( pInputMesh->GetNumFaces() + nNumMaps ) * 3,
						D3DXMESH_32BIT,
						Decl,
						pd3dDevice,
						&pPatchMesh );

					if( FAILED( hr ) )
						goto cleanup;

					hr = pPatchMesh->LockVertexBuffer( 0, ( LPVOID* )&pPatchVBData );
					if( SUCCEEDED( hr ) )
						hr = pPatchMesh->LockIndexBuffer( 0, ( LPVOID* )&pdwPatchIBData );

					if( pPatchVBData && pdwPatchIBData )
					{
						ZeroMemory( pPatchVBData, sizeof( SHADOWVERT ) * ( pInputMesh->GetNumFaces() + nNumMaps ) *
							3 );
						ZeroMemory( pdwPatchIBData, sizeof( DWORD ) * ( nNextIndex + 3 * nNumMaps * 7 ) );

						// Copy the data from one mesh to the other

						CopyMemory( pPatchVBData, pNewVBData, sizeof( SHADOWVERT ) * pInputMesh->GetNumFaces() * 3 );
						CopyMemory( pdwPatchIBData, pdwNewIBData, sizeof( DWORD ) * nNextIndex );
					}
					else
					{
						// Some serious error is preventing us from locking.
						// Abort and return error.

						pPatchMesh->Release();
						goto cleanup;
					}

					// Replace pNewMesh with the updated one.  Then the code
					// can continue working with the pNewMesh pointer.

					pNewMesh->UnlockVertexBuffer();
					pNewMesh->UnlockIndexBuffer();
					pNewVBData = pPatchVBData;
					pdwNewIBData = pdwPatchIBData;
					pNewMesh->Release();
					pNewMesh = pPatchMesh;

					// Now, we iterate through the edge mapping table and
					// for each shared edge, we generate a quad.
					// For each non-shared edge, we patch the opening
					// with new faces.

					// nNextVertex is the index of the next vertex.
					int nNextVertex = pInputMesh->GetNumFaces() * 3;

					for( int i = 0; i < nNumMaps; ++i )
					{
						if( pMapping[i].m_anOldEdge[0] != -1 &&
							pMapping[i].m_anOldEdge[1] != -1 )
						{
							// If the 2nd new edge indexes is -1,
							// this edge is a non-shared one.
							// We patch the opening by creating new
							// faces.
							if( pMapping[i].m_aanNewEdge[1][0] == -1 ||  // must have only one new edge
								pMapping[i].m_aanNewEdge[1][1] == -1 )
							{
								// Find another non-shared edge that
								// shares a vertex with the current edge.
								for( int i2 = i + 1; i2 < nNumMaps; ++i2 )
								{
									if( pMapping[i2].m_anOldEdge[0] != -1 &&       // must have a valid old edge
										pMapping[i2].m_anOldEdge[1] != -1 &&
										( pMapping[i2].m_aanNewEdge[1][0] == -1 || // must have only one new edge
										pMapping[i2].m_aanNewEdge[1][1] == -1 ) )
									{
										int nVertShared = 0;
										if( pMapping[i2].m_anOldEdge[0] == pMapping[i].m_anOldEdge[1] )
											++nVertShared;
										if( pMapping[i2].m_anOldEdge[1] == pMapping[i].m_anOldEdge[0] )
											++nVertShared;

										if( 2 == nVertShared )
										{
											// These are the last two edges of this particular
											// opening. Mark this edge as shared so that a degenerate
											// quad can be created for it.

											pMapping[i2].m_aanNewEdge[1][0] = pMapping[i].m_aanNewEdge[0][0];
											pMapping[i2].m_aanNewEdge[1][1] = pMapping[i].m_aanNewEdge[0][1];
											break;
										}
										else if( 1 == nVertShared )
										{
											// nBefore and nAfter tell us which edge comes before the other.
											int nBefore, nAfter;
											if( pMapping[i2].m_anOldEdge[0] == pMapping[i].m_anOldEdge[1] )
											{
												nBefore = i;
												nAfter = i2;
											}
											else
											{
												nBefore = i2;
												nAfter = i;
											}

											// Found such an edge. Now create a face along with two
											// degenerate quads from these two edges.

											pNewVBData[nNextVertex] = pNewVBData[pMapping[nAfter].m_aanNewEdge[0][1]];
											pNewVBData[nNextVertex +
												1] = pNewVBData[pMapping[nBefore].m_aanNewEdge[0][1]];
											pNewVBData[nNextVertex +
												2] = pNewVBData[pMapping[nBefore].m_aanNewEdge[0][0]];
											// Recompute the normal
											D3DXVECTOR3 v1 = pNewVBData[nNextVertex + 1].Position -
												pNewVBData[nNextVertex].Position;
											D3DXVECTOR3 v2 = pNewVBData[nNextVertex + 2].Position -
												pNewVBData[nNextVertex + 1].Position;
											D3DXVec3Normalize( &v1, &v1 );
											D3DXVec3Normalize( &v2, &v2 );
											D3DXVec3Cross( &pNewVBData[nNextVertex].Normal, &v1, &v2 );
											pNewVBData[nNextVertex + 1].Normal = pNewVBData[nNextVertex +
												2].Normal = pNewVBData[nNextVertex].Normal;

											pdwNewIBData[nNextIndex] = nNextVertex;
											pdwNewIBData[nNextIndex + 1] = nNextVertex + 1;
											pdwNewIBData[nNextIndex + 2] = nNextVertex + 2;

											// 1st quad

											pdwNewIBData[nNextIndex + 3] = pMapping[nBefore].m_aanNewEdge[0][1];
											pdwNewIBData[nNextIndex + 4] = pMapping[nBefore].m_aanNewEdge[0][0];
											pdwNewIBData[nNextIndex + 5] = nNextVertex + 1;

											pdwNewIBData[nNextIndex + 6] = nNextVertex + 2;
											pdwNewIBData[nNextIndex + 7] = nNextVertex + 1;
											pdwNewIBData[nNextIndex + 8] = pMapping[nBefore].m_aanNewEdge[0][0];

											// 2nd quad

											pdwNewIBData[nNextIndex + 9] = pMapping[nAfter].m_aanNewEdge[0][1];
											pdwNewIBData[nNextIndex + 10] = pMapping[nAfter].m_aanNewEdge[0][0];
											pdwNewIBData[nNextIndex + 11] = nNextVertex;

											pdwNewIBData[nNextIndex + 12] = nNextVertex + 1;
											pdwNewIBData[nNextIndex + 13] = nNextVertex;
											pdwNewIBData[nNextIndex + 14] = pMapping[nAfter].m_aanNewEdge[0][0];

											// Modify mapping entry i2 to reflect the third edge
											// of the newly added face.

											if( pMapping[i2].m_anOldEdge[0] == pMapping[i].m_anOldEdge[1] )
											{
												pMapping[i2].m_anOldEdge[0] = pMapping[i].m_anOldEdge[0];
											}
											else
											{
												pMapping[i2].m_anOldEdge[1] = pMapping[i].m_anOldEdge[1];
											}
											pMapping[i2].m_aanNewEdge[0][0] = nNextVertex + 2;
											pMapping[i2].m_aanNewEdge[0][1] = nNextVertex;

											// Update next vertex/index positions

											nNextVertex += 3;
											nNextIndex += 15;

											break;
										}
									}
								}
							}
							else
							{
								// This is a shared edge.  Create the degenerate quad.

								// First triangle
								pdwNewIBData[nNextIndex++] = pMapping[i].m_aanNewEdge[0][1];
								pdwNewIBData[nNextIndex++] = pMapping[i].m_aanNewEdge[0][0];
								pdwNewIBData[nNextIndex++] = pMapping[i].m_aanNewEdge[1][0];

								// Second triangle
								pdwNewIBData[nNextIndex++] = pMapping[i].m_aanNewEdge[1][1];
								pdwNewIBData[nNextIndex++] = pMapping[i].m_aanNewEdge[1][0];
								pdwNewIBData[nNextIndex++] = pMapping[i].m_aanNewEdge[0][0];
							}
						}
					}
				}

cleanup:;
				if( pNewVBData )
				{
					pNewMesh->UnlockVertexBuffer();
					pNewVBData = NULL;
				}
				if( pdwNewIBData )
				{
					pNewMesh->UnlockIndexBuffer();
					pdwNewIBData = NULL;
				}

				if( SUCCEEDED( hr ) )
				{
					// At this time, the output mesh may have an index buffer
					// bigger than what is actually needed, so we create yet
					// another mesh with the exact IB size that we need and
					// output it.  This mesh also uses 16-bit index if
					// 32-bit is not necessary.



					bool bNeed32Bit = ( pInputMesh->GetNumFaces() + nNumMaps ) * 3 > 65535;
					ID3DXMesh* pFinalMesh;
					hr = D3DXCreateMesh( nNextIndex / 3,  // Exact number of faces
						( pInputMesh->GetNumFaces() + nNumMaps ) * 3,
						D3DXMESH_WRITEONLY | ( bNeed32Bit ? D3DXMESH_32BIT : 0 ),
						Decl,
						pd3dDevice,
						&pFinalMesh );
					if( SUCCEEDED( hr ) )
					{
						pNewMesh->LockVertexBuffer( 0, ( LPVOID* )&pNewVBData );
						pNewMesh->LockIndexBuffer( 0, ( LPVOID* )&pdwNewIBData );

						SHADOWVERT* pFinalVBData = NULL;
						WORD* pwFinalIBData = NULL;

						pFinalMesh->LockVertexBuffer( 0, ( LPVOID* )&pFinalVBData );
						pFinalMesh->LockIndexBuffer( 0, ( LPVOID* )&pwFinalIBData );

						if( pNewVBData && pdwNewIBData && pFinalVBData && pwFinalIBData )
						{
							CopyMemory( pFinalVBData, pNewVBData, sizeof( SHADOWVERT ) *
								( pInputMesh->GetNumFaces() + nNumMaps ) * 3 );

							if( bNeed32Bit )
								CopyMemory( pwFinalIBData, pdwNewIBData, sizeof( DWORD ) * nNextIndex );
							else
							{
								for( int i = 0; i < nNextIndex; ++i )
									pwFinalIBData[i] = ( WORD )pdwNewIBData[i];
							}
						}

						if( pNewVBData )
							pNewMesh->UnlockVertexBuffer();
						if( pdwNewIBData )
							pNewMesh->UnlockIndexBuffer();
						if( pFinalVBData )
							pFinalMesh->UnlockVertexBuffer();
						if( pwFinalIBData )
							pFinalMesh->UnlockIndexBuffer();

						// Release the old
						pNewMesh->Release();
						pNewMesh = pFinalMesh;
					}

					*ppOutMesh = pNewMesh;
				}
				else
					pNewMesh->Release();
			}
			delete[] pMapping;
		}
		else
			hr = E_OUTOFMEMORY;
	}
	else
		hr = E_FAIL;

	if( pVBData )
		pInputMesh->UnlockVertexBuffer();

	if( pdwIBData )
		pInputMesh->UnlockIndexBuffer();

	delete[] pdwPtRep;
	pInputMesh->Release();

	return hr;
}
int Renderer::FindEdgeInMappingTable( int nV1, int nV2, CEdgeMapping* pMapping, int nCount )
{
	for( int i = 0; i < nCount; ++i )
	{
		// If both vertex indexes of the old edge in mapping entry are -1, then
		// we have searched every valid entry without finding a match.  Return
		// this index as a newly created entry.
		if( ( pMapping[i].m_anOldEdge[0] == -1 && pMapping[i].m_anOldEdge[1] == -1 ) ||

			// Or if we find a match, return the index.
			( pMapping[i].m_anOldEdge[1] == nV1 && pMapping[i].m_anOldEdge[0] == nV2 ) )
		{
			return i;
		}
	}

	return -1;  // We should never reach this line
}

bool Renderer::AddOctreeObjectToRender(Drawable* a_pObject)
{
	if(!a_pObject)
	{
		return false;
	}
	
	//Add to the list to be rendered, if its not already in there
	for(DrawableObjectList::iterator iter = m_octreeObjectsToRender.begin(); iter != m_octreeObjectsToRender.end(); iter++)
	{
		Drawable* pElem = *iter;
		if(pElem == a_pObject)
		{
			//Item already in the render list, dont add
			return false;
		}
	}

	m_octreeObjectsToRender.push_back(a_pObject);

	return true;
}